/**
 * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 *
 *https://leetcode.cn/problems/diagonal-traverse/
 * 思路:按照对角线遍历
 */
class FindDiagonalOrder {
    public int[] findDiagonalOrder(int[][] mat) {
        int row=mat.length;
        int coll=mat[0].length;
        int[] ans=new int[row*coll];
        int tmp=0;
        int k=0;
        for(int i=0;i<row+coll-1;i++){
            if(i%2==1){
                int x=i<coll?0:i-coll+1;
                int y=i<coll?i:coll-1;
                while(x<row&&y>=0){
                    ans[k++]=mat[x++][y--];
                }
            }else{
                int x=i<row?i:row-1;
                int y=i<row?0:i-row+1;
                while(x>=0&&y<coll){
                    ans[k++]=mat[x--][y++];
                }
            }
        }
        return ans;
    }
}